//
//  7.斐波那契数列.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：⼤家都知道斐波那契数列，现在要求输⼊⼀个整数n，请你输出斐波那契数列的第n项。（n<=39）
 思路：f(n) = f(n-1) + f(n-2) n > 1
 */
func offer_7() {
    print(Solution().Fibonacci(4))
}

fileprivate class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型
     * @return int整型
     */
    func Fibonacci(_ n: Int) -> Int {
        // write code here
        guard n > 1 else { return n }
        var first = 0
        var second = 1
        var num: Int = 0
        for _ in 2...n {
            num = first + second
            first = second
            second = num
        }
        return num
    }
}
